#include <stdio.h>
#include <stdlib.h>
#define len 50
int sort_arry[len] = {5,3,9,4,2,8,7,1,6,10};

int partition(int start, int end);
int order_statistic(int start, int end, int k);

// vs git2019.5.16
// void swap(int a,int b)
// {
//     int temp;
//     temp=a;
//     a=b;
//     b=temp;
// }

int partition(int start, int end)
{
int mid, i, j, pivot,temp;

    if (start > end) return 0;

    pivot = sort_arry[start];

    i = start+1;
    j = end;
    while(i!=j)
    {
        while(sort_arry[j] > pivot && i < j)
            j--;
        while(sort_arry[i] < pivot && i < j)
            i++;

        if(i < j)
        {
            temp = sort_arry[i];
            sort_arry[i] = sort_arry[j];
            sort_arry[j] = temp;
        }
    }
if(pivot > sort_arry[i]){
    sort_arry[start] = sort_arry[i];
    sort_arry[i] = pivot;
    printf("过程:");
    }
 for (int i = 0; i < 10; ++i)
    {
        printf("%d",sort_arry[i]);
    }
    printf("\n");
    return i-start+1 ;
    // for(int i = end; i > mid; i--)


    //     if(sort_arry[i] < sort_arry[start])
    //     {
    //         for(int j = start +1 ; j < mid; j++)
    //          if(sort_arry[j] < sort_arry[start])
    //             swap(ort_arry[i],ort_arry[j]);
    //     }else
    //     result_sort_arry[mid+i-1] = sort_arry[i];

    
}

int order_statistic(int start, int end, int k)
{int i =0 ;
    
     i = partition(start,end);
     printf("start:%d end:%d i:%d",start,end,i);
     printf("\n");
    if (k == i)
        return sort_arry[start + i-1];
    else if (k > i)
        order_statistic(i,end,k-i);
    else
        order_statistic(start,end-i,k);
}
 int main(void)
 {int temp = 1;
     /* code */
    
    
    temp = order_statistic(0,9,8);
    printf("结果:");
    printf("%d",temp);
    printf("\n");
    printf("数组：");
    for (int i = 0; i < 10; ++i)
    {
        printf("%d",sort_arry[i]);
    }

 //     return 0;
 }
// int partition(int start, int end)
// {
//     从 a[start..end] 中选取一个 pivot 元素（比如选 a[start] 为pivot）;

//     在一个循环中移动 a[start..end] 的数据，将 a[start..end] 分成两半，

//     使 a[start..mid - 1] 比 pivot 元素小，a[mid + 1..end] 比 pivot 元素大，而 a[mid] 就是 pivot 元素;

//     return mid;
// }

//  从 start 到 end 之间找出第 k 小的元素 
// int order_statistic(int start, int end, int k)
// {
//     用 partition 函数把序列分成两半，中间的 pivot 元素是序列中的
//         第 i 个;
//     if (k == i)
//         返回找到的元素;
//     else if (k > i)
//         从后半部分找出第 k - i 小的元素并返回;
//     else
//         从前半部分找出第 k 小的元素并返回;
// }